/*

给定一个 N 叉树，找到其最大深度。

最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。

例如，给定一个 3叉树 :


// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    int MaxDepth = -1;
    void Travel_Pre(Node* node,int & MaxDepth,int curDepth)
    {
        if(node == 0)
            return;
        
        if(node->children.size()==0)
        {
            MaxDepth = MaxDepth<curDepth?curDepth:MaxDepth;
        }
        for(int i=0;i<node->children.size();i++)
        {
            Travel_Pre(node->children[i], MaxDepth, curDepth +1);
        }
    }
    int maxDepth(Node* root) 
    {
        if(root == 0)
        {
            return 0;
        }
        Travel_Pre(root,MaxDepth,1);
        return MaxDepth;
        
    }
};